﻿#include <bitset>
#include <string>

#include "HaSh.h"
#include "unordered_set.h"
#include "unordered_map.h"
#include "bitset.h"
#include "BloomFilter.h"

void test1()
{
	hash_table::HashTable<int, int> t;
	t.Insert({ 1, 1 });
	t.Insert({ 3, 1 });
	t.Insert({ 4, 1 });
	t.Insert({ 13, 1 });
	t.Insert({ 6, 1 });

	t.Print();
	t.Erase(3);
	if (t.Find(3))
		cout << "3存在" << endl;
	else
		cout << "3不存在" << endl;
	t.Insert({ 3, 1 });
	if (t.Find(3))
		cout << "3存在" << endl;
	else
		cout << "3不存在" << endl;
}

void test2()
{
	hash_table::HashTable<string, string> t;
	// t["sort"] = "排序";
	t.Insert({ "sort", "排序"});
	t.Insert({ "abc", "排序"});
	t.Insert({ "acb", "排序"});
	t.Print();
}

void test3()
{
	hash_bucket1::HashTable<int, int> ht;
	int a[] = { 4,14,24,34,5,7,1,15,25,3 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(13, 13));

	cout << ht.Find(4) << endl;
	ht.Erase(4);
	cout << ht.Find(4) << endl;
}

void test4()
{
	hash_bucket1::HashTable<string, int> ht;
	string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	for (auto& e : arr)
	{
		//auto ret = ht.Find(e);
		hash_bucket1::HashNode<string, int>* ret = ht.Find(e);
		if (ret)
		{
			ret->_kv.second++;
		}
		else
		{
			ht.Insert(make_pair(e, 1));
		}
	}
	int i = 0;
}

void test5()
{
	MyUnorderSet::unordered_set<int> us;
	us.insert(5);
	us.insert(15);
	us.insert(52);
	us.insert(3);

	MyUnorderSet::unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		// *it += 5;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : us)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test6()
{
	MyUnorderMap::unordered_map<string, string> dict;
	dict.insert(make_pair("sort", ""));
	dict.insert(make_pair("string", ""));
	dict.insert(make_pair("insert", ""));

	for (auto& kv : dict)
	{
		// kv.first += 'x';
		kv.second += 'x';

		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

	string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	MyUnorderMap::unordered_map<string, int> count_map;
	for (auto& e : arr)
	{
		count_map[e]++;
	}

	for (auto& kv : count_map)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;
}

void test7()
{
	bit_set::bitset<100> bits;
	bits.set(10);
	bits.set(31);
	bits.set(43);

	cout << bits.test(1) << endl;
	cout << bits.test(10) << endl;
	cout << bits.test(31) << endl;
	cout << bits.test(43) << endl;
	cout << bits.test(41) << endl;

	bits.reset(31);

	cout << endl;

	cout << bits.test(1) << endl;
	cout << bits.test(10) << endl;
	cout << bits.test(31) << endl;
	cout << bits.test(43) << endl;
	cout << bits.test(41) << endl;
}

void test8()
{
	// std::bitset<-1> bits;// 开四十二亿个空间，看会不会挂掉
	/*
		数组的总大小不得超过 0x7fffffff 字节
	*/
}

// std::bitset<-1> bits;// 开四十二亿个空间，看会不会挂掉，虽然放在全局，仍然会
/*
	无法从以前的错误中恢复；正在停止编译

	数组的总大小不得超过 0x7fffffff 字
*/

void test9()
{
	int a[] = { 1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 };
	bit_set::twobitset<100> bs;
	for (auto e : a)
	{
		bs.set(e);
	}
	bs.PrintOnce();
}

void test10()
{
	BloomFilter<100> bf;
	bf.Set("猪八戒");
	bf.Set("沙悟净");
	bf.Set("孙悟空");
	bf.Set("二郎神");

	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("沙悟净") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("二郎神") << endl;
	cout << bf.Test("二郎神1") << endl;
	cout << bf.Test("二郎神2") << endl;
	cout << bf.Test("二郎神 ") << endl;
	cout << bf.Test("太白晶星") << endl;
}

void test11()
{
	srand(time(0));
	const size_t N = 100000;
	BloomFilter<N * 10> bf;

	std::vector<std::string> v1;
	//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	std::string url = "猪八戒";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是不一样
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v2.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		//string url = "zhihu.com";
		string url = "孙悟空";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

int main()
{
	// test1();
	// test2();
	// test3();
	// test4();
	// test5();
	// test6();
	// test7();
	// test8();
	// test9();
	// test10();
	test11();

	return 0;
}